﻿#pragma execution_character_set("utf-8")
#include "findway.h"
#include <queue>
#include <cmath>
#include <algorithm>
#include <QVector>
#include <cstdio>
#include <windows.h>

#define MAX_VERTEX_NUM 210


struct Node {
    int vertex;
    int g_cost; // 从起点到当前节点的实际代价
    int f_cost; // f = g + h，其中 h 是启发式代价
    bool operator>(const Node &other) const {
        return f_cost > other.f_cost;
    }
};

FindWay::FindWay(QObject *parent) : QObject(parent) //构造函数
{
    mgraph.vexnum = MAX_VERTEX_NUM;                //初始化顶点的最大值
    for (int i = 0; i < MAX_VERTEX_NUM; i++) {
        for (int j = 0; j < MAX_VERTEX_NUM; j++) {
            if (i == j)
                mgraph.arcs[i][j].adj = 0;    //自环的权重
            else
                mgraph.arcs[i][j].adj = INF;  //其余边的初始权重无限大
            mgraph.arcs[i][j].kind = true;    //初始边的类型：无向图
        }
    }
    this->CreateGraph();  // 创建图的具体边和权重
}

void FindWay::CreateGraph()   //创建图，每一项都是在定义边的权重，但是这个顶点有什么特殊的含义？
{
    mgraph.arcs[1][101].adj = mgraph.arcs[101][1].adj =60;   //因为是无向图所以有两次边的权重赋值
    mgraph.arcs[101][2].adj = mgraph.arcs[2][101].adj =5;
    mgraph.arcs[2][3].adj = mgraph.arcs[3][2].adj =30 ;
    mgraph.arcs[4][3].adj = mgraph.arcs[3][4].adj =10 ;
    mgraph.arcs[3][102].adj = mgraph.arcs[102][3].adj =5 ;
    mgraph.arcs[102][26].adj = mgraph.arcs[26][102].adj =50 ;
    mgraph.arcs[102][127].adj = mgraph.arcs[127][102].adj =80 ;
    mgraph.arcs[127][5].adj = mgraph.arcs[5][127].adj =70 ;
    mgraph.arcs[5][6].adj = mgraph.arcs[6][5].adj =60 ;
    mgraph.arcs[6][103].adj = mgraph.arcs[103][6].adj =80 ; mgraph.arcs[6][103].kind = mgraph.arcs[103][6].kind = false;
    mgraph.arcs[127][128].adj = mgraph.arcs[128][127].adj =40 ; mgraph.arcs[127][128].kind = mgraph.arcs[128][127].kind = false;
    mgraph.arcs[26][106].adj = mgraph.arcs[106][26].adj =40 ;
    mgraph.arcs[106][128].adj = mgraph.arcs[128][106].adj =20 ;
    mgraph.arcs[128][103].adj = mgraph.arcs[103][128].adj =110 ;
    mgraph.arcs[103][30].adj = mgraph.arcs[30][103].adj =80 ;
    mgraph.arcs[26][7].adj = mgraph.arcs[7][26].adj =140 ;
    mgraph.arcs[26][129].adj = mgraph.arcs[129][26].adj =70 ; mgraph.arcs[26][129].kind = mgraph.arcs[129][26].kind = false;
    mgraph.arcs[106][27].adj = mgraph.arcs[27][106].adj =90 ;
    mgraph.arcs[103][28].adj = mgraph.arcs[28][103].adj =80 ;
    mgraph.arcs[26][7].adj = mgraph.arcs[7][26].adj =140 ;
    mgraph.arcs[26][129].adj = mgraph.arcs[129][26].adj =70 ;
    mgraph.arcs[106][27].adj = mgraph.arcs[27][106].adj =90 ;
    mgraph.arcs[103][28].adj = mgraph.arcs[28][103].adj =50 ;
    mgraph.arcs[28][104].adj = mgraph.arcs[104][28].adj =30 ;
    mgraph.arcs[129][27].adj = mgraph.arcs[27][129].adj =60 ;
    mgraph.arcs[27][105].adj = mgraph.arcs[105][27].adj =90 ;
    mgraph.arcs[105][104].adj = mgraph.arcs[104][105].adj =40 ;
    mgraph.arcs[7][8].adj = mgraph.arcs[8][7].adj =30 ;
    mgraph.arcs[8][9].adj = mgraph.arcs[9][8].adj =60 ;
    mgraph.arcs[7][25].adj = mgraph.arcs[25][7].adj =30 ;
    mgraph.arcs[25][24].adj = mgraph.arcs[24][25].adj =50 ;
    mgraph.arcs[24][123].adj = mgraph.arcs[123][24].adj =120 ; mgraph.arcs[24][123].kind = mgraph.arcs[123][24].kind =false ; //不能够通过自行车到达
    mgraph.arcs[104][29].adj = mgraph.arcs[29][104].adj =35 ;
    mgraph.arcs[129][123].adj = mgraph.arcs[123][129].adj =80 ; mgraph.arcs[123][129].kind = mgraph.arcs[129][123].kind = false;
    mgraph.arcs[123][33].adj = mgraph.arcs[33][123].adj =100 ;
    mgraph.arcs[33][29].adj = mgraph.arcs[29][33].adj =70 ;
    mgraph.arcs[105][33].adj = mgraph.arcs[33][105].adj =30 ;
    mgraph.arcs[123][124].adj = mgraph.arcs[124][123].adj =35 ; mgraph.arcs[123][124].kind = mgraph.arcs[124][123].kind = false;
    mgraph.arcs[33][32].adj = mgraph.arcs[32][33].adj =30 ;
    mgraph.arcs[29][31].adj = mgraph.arcs[31][29].adj =40 ;
    mgraph.arcs[9][10].adj = mgraph.arcs[10][9].adj =60 ;
    mgraph.arcs[11][10].adj = mgraph.arcs[10][11].adj =30 ;
    mgraph.arcs[11][21].adj = mgraph.arcs[21][11].adj =60 ;
    mgraph.arcs[21][107].adj = mgraph.arcs[107][21].adj =60 ;
    mgraph.arcs[107][23].adj = mgraph.arcs[23][107].adj =50 ;
    mgraph.arcs[23][24].adj = mgraph.arcs[24][23].adj =30 ;
    mgraph.arcs[107][22].adj = mgraph.arcs[22][107].adj =55 ;
    mgraph.arcs[22][207].adj = mgraph.arcs[207][22].adj =40 ;
    mgraph.arcs[207][125].adj = mgraph.arcs[125][207].adj =60 ;
    mgraph.arcs[125][124].adj = mgraph.arcs[124][125].adj =10 ; mgraph.arcs[125][124].kind = mgraph.arcs[125][123].kind = false;
    mgraph.arcs[124][32].adj = mgraph.arcs[32][124].adj =90 ;
    mgraph.arcs[32][31].adj = mgraph.arcs[31][32].adj =80 ;
    mgraph.arcs[124][122].adj = mgraph.arcs[122][124].adj =90 ; mgraph.arcs[122][124].kind = mgraph.arcs[124][122].kind = false;
    mgraph.arcs[32][119].adj = mgraph.arcs[119][32].adj =60 ;
    mgraph.arcs[121][31].adj = mgraph.arcs[31][121].adj =40 ;
    mgraph.arcs[119][120].adj = mgraph.arcs[120][119].adj =20 ;
    mgraph.arcs[120][121].adj = mgraph.arcs[121][120].adj =50 ;
    mgraph.arcs[122][119].adj = mgraph.arcs[119][122].adj =90 ;
    mgraph.arcs[122][109].adj = mgraph.arcs[109][122].adj =60 ;
    mgraph.arcs[109][207].adj = mgraph.arcs[207][109].adj =30 ;
    mgraph.arcs[107][20].adj = mgraph.arcs[20][107].adj =60 ;
    mgraph.arcs[20][207].adj = mgraph.arcs[207][20].adj =35 ;
    mgraph.arcs[107][110].adj = mgraph.arcs[110][107].adj =40 ;
    mgraph.arcs[110][112].adj = mgraph.arcs[112][110].adj =15 ;
    mgraph.arcs[112][111].adj = mgraph.arcs[111][112].adj =15 ;
    mgraph.arcs[11][108].adj = mgraph.arcs[108][11].adj =40 ;
    mgraph.arcs[108][12].adj = mgraph.arcs[12][108].adj =30 ;
    mgraph.arcs[12][13].adj = mgraph.arcs[13][12].adj =70 ;
    mgraph.arcs[13][14].adj = mgraph.arcs[14][13].adj =30 ;
    mgraph.arcs[109][115].adj = mgraph.arcs[115][109].adj =40 ;
    mgraph.arcs[115][116].adj = mgraph.arcs[116][115].adj =35 ;
    mgraph.arcs[116][117].adj = mgraph.arcs[117][116].adj =40 ;
    mgraph.arcs[112][18].adj = mgraph.arcs[18][112].adj =40 ;
    mgraph.arcs[18][109].adj = mgraph.arcs[109][18].adj =60 ;
    mgraph.arcs[113][17].adj = mgraph.arcs[17][113].adj =50 ;
    mgraph.arcs[115][17].adj = mgraph.arcs[17][115].adj =40 ;
    mgraph.arcs[114][16].adj = mgraph.arcs[16][114].adj =40 ;
    mgraph.arcs[116][16].adj = mgraph.arcs[16][116].adj =50 ;
    mgraph.arcs[15][117].adj = mgraph.arcs[117][15].adj =100 ;
    mgraph.arcs[15][191].adj = mgraph.arcs[191][15].adj =10 ;
    mgraph.arcs[111][113].adj = mgraph.arcs[113][111].adj =30 ;
    mgraph.arcs[113][114].adj = mgraph.arcs[114][113].adj =30 ;
    mgraph.arcs[114][15].adj = mgraph.arcs[15][114].adj =40 ;
    mgraph.arcs[108][19].adj = mgraph.arcs[19][108].adj =60 ;
    mgraph.arcs[19][110].adj = mgraph.arcs[110][19].adj =50 ;
    mgraph.arcs[12][111].adj = mgraph.arcs[111][12].adj = 110;
    mgraph.arcs[14][15].adj = mgraph.arcs[15][14].adj =110;
    mgraph.arcs[14][190].adj = mgraph.arcs[190][14].adj =10;
    mgraph.arcs[117][118].adj = mgraph.arcs[118][117].adj =80 ;
    mgraph.arcs[118][34].adj = mgraph.arcs[34][118].adj =80 ;
    mgraph.arcs[120][131].adj = mgraph.arcs[131][120].adj =60 ;
    mgraph.arcs[131][40].adj = mgraph.arcs[40][131].adj =30 ;
    mgraph.arcs[131][35].adj = mgraph.arcs[35][131].adj =100 ;
    mgraph.arcs[35][37].adj = mgraph.arcs[37][35].adj =30 ;
    mgraph.arcs[35][126].adj = mgraph.arcs[126][35].adj =40 ;
    mgraph.arcs[118][36].adj = mgraph.arcs[36][118].adj =100 ;
    mgraph.arcs[36][130].adj = mgraph.arcs[130][36].adj =20 ;
    mgraph.arcs[36][126].adj = mgraph.arcs[126][36].adj =60 ;
    mgraph.arcs[130][126].adj = mgraph.arcs[126][130].adj =50 ;
    mgraph.arcs[38][126].adj = mgraph.arcs[126][38].adj =20 ;
    mgraph.arcs[38][39].adj = mgraph.arcs[39][38].adj =30 ;
    mgraph.arcs[38][132].adj = mgraph.arcs[132][38].adj =50 ;
    mgraph.arcs[39][132].adj = mgraph.arcs[132][39].adj =50 ;
    mgraph.arcs[130][39].adj = mgraph.arcs[39][130].adj =50 ;
    mgraph.arcs[6][138].adj = mgraph.arcs[138][6].adj =140 ;
    mgraph.arcs[30][41].adj = mgraph.arcs[41][30].adj =40 ;
    mgraph.arcs[137][138].adj = mgraph.arcs[138][137].adj =10 ;
    mgraph.arcs[137][136].adj = mgraph.arcs[136][137].adj =60 ;
    mgraph.arcs[136][139].adj = mgraph.arcs[139][136].adj =55 ;
    mgraph.arcs[135][139].adj = mgraph.arcs[139][135].adj =70 ;
    mgraph.arcs[135][134].adj = mgraph.arcs[134][135].adj =20 ;
    mgraph.arcs[134][41].adj = mgraph.arcs[41][134].adj =60 ;
    mgraph.arcs[139][145].adj = mgraph.arcs[145][139].adj =140 ;
    mgraph.arcs[145][45].adj = mgraph.arcs[45][145].adj =120 ;
    mgraph.arcs[45][44].adj = mgraph.arcs[44][45].adj =60 ;
    mgraph.arcs[44][144].adj = mgraph.arcs[144][44].adj =30 ;
    mgraph.arcs[142][143].adj = mgraph.arcs[143][142].adj =40 ;
    mgraph.arcs[144][143].adj = mgraph.arcs[143][144].adj =30 ;
    mgraph.arcs[142][141].adj = mgraph.arcs[141][142].adj =30 ;
    mgraph.arcs[140][141].adj = mgraph.arcs[141][140].adj =70 ;
    mgraph.arcs[42][135].adj = mgraph.arcs[135][42].adj =60 ;
    mgraph.arcs[42][140].adj = mgraph.arcs[140][42].adj =60 ;
    mgraph.arcs[139][43].adj = mgraph.arcs[43][139].adj =60 ;
    mgraph.arcs[43][142].adj = mgraph.arcs[142][43].adj =60 ;
    mgraph.arcs[140][146].adj = mgraph.arcs[146][140].adj =70 ;
    mgraph.arcs[149][44].adj = mgraph.arcs[44][149].adj =70 ;
    mgraph.arcs[153][45].adj = mgraph.arcs[45][153].adj =80 ;
    mgraph.arcs[121][146].adj = mgraph.arcs[146][121].adj =100 ;
    mgraph.arcs[81][146].adj = mgraph.arcs[146][81].adj =30 ;
    mgraph.arcs[81][147].adj = mgraph.arcs[147][81].adj =30 ;
    mgraph.arcs[146][148].adj = mgraph.arcs[148][146].adj =60 ;
    mgraph.arcs[148][147].adj = mgraph.arcs[147][148].adj =50 ;
    mgraph.arcs[147][149].adj = mgraph.arcs[149][147].adj =80 ;
    mgraph.arcs[149][153].adj = mgraph.arcs[153][149].adj =60 ;
    mgraph.arcs[153][69].adj = mgraph.arcs[69][153].adj =130 ;
    mgraph.arcs[176][69].adj = mgraph.arcs[69][176].adj =150 ;
    mgraph.arcs[83][69].adj = mgraph.arcs[69][83].adj =350 ;
    mgraph.arcs[176][72].adj = mgraph.arcs[72][176].adj =100 ;
    mgraph.arcs[71][72].adj = mgraph.arcs[72][71].adj =50 ;
    mgraph.arcs[71][70].adj = mgraph.arcs[70][71].adj =100 ;
    mgraph.arcs[148][47].adj = mgraph.arcs[47][148].adj =60 ;
    mgraph.arcs[47][46].adj = mgraph.arcs[46][47].adj =60 ;
    mgraph.arcs[149][46].adj = mgraph.arcs[46][149].adj =70 ;
    mgraph.arcs[47][48].adj = mgraph.arcs[48][47].adj =40 ;
    mgraph.arcs[154][48].adj = mgraph.arcs[48][154].adj =40 ;
    mgraph.arcs[153][154].adj = mgraph.arcs[154][153].adj =110 ;
    mgraph.arcs[150][37].adj = mgraph.arcs[37][150].adj =100 ;
    mgraph.arcs[150][48].adj = mgraph.arcs[48][150].adj =70 ;
    mgraph.arcs[150][151].adj = mgraph.arcs[151][150].adj =60 ;
    mgraph.arcs[151][48].adj = mgraph.arcs[48][151].adj =60 ;
    mgraph.arcs[48][49].adj = mgraph.arcs[49][48].adj =70 ;
    mgraph.arcs[151][49].adj = mgraph.arcs[49][151].adj =70 ;
    mgraph.arcs[151][132].adj = mgraph.arcs[132][151].adj =60 ;
    mgraph.arcs[130][156].adj = mgraph.arcs[156][130].adj =60 ;
    mgraph.arcs[126][39].adj = mgraph.arcs[39][126].adj =30 ;
    mgraph.arcs[39][50].adj = mgraph.arcs[50][39].adj =60 ;
    mgraph.arcs[156][39].adj = mgraph.arcs[39][156].adj =60 ;
    mgraph.arcs[156][50].adj = mgraph.arcs[50][156].adj =60 ;
    mgraph.arcs[152][82].adj = mgraph.arcs[82][152].adj =80 ;
    mgraph.arcs[152][50].adj = mgraph.arcs[50][152].adj =90 ;
    mgraph.arcs[151][152].adj = mgraph.arcs[152][151].adj =60 ;
    mgraph.arcs[50][63].adj = mgraph.arcs[63][50].adj =180 ;
    mgraph.arcs[156][51].adj = mgraph.arcs[51][156].adj =70 ;
    mgraph.arcs[157][50].adj = mgraph.arcs[50][157].adj =40 ;
    mgraph.arcs[157][51].adj = mgraph.arcs[51][157].adj =40 ;
    mgraph.arcs[51][52].adj = mgraph.arcs[52][51].adj =30 ;
    mgraph.arcs[158][52].adj = mgraph.arcs[52][158].adj =40 ;
    mgraph.arcs[158][53].adj = mgraph.arcs[53][158].adj =20 ;
    mgraph.arcs[53][52].adj = mgraph.arcs[52][53].adj =50 ;
    mgraph.arcs[53][159].adj = mgraph.arcs[159][53].adj =15 ;
    mgraph.arcs[53][161].adj = mgraph.arcs[161][53].adj =30 ;
    mgraph.arcs[159][161].adj = mgraph.arcs[161][159].adj =30 ;
    mgraph.arcs[161][54].adj = mgraph.arcs[54][161].adj =20 ;
    mgraph.arcs[159][54].adj = mgraph.arcs[54][159].adj =40 ;
    mgraph.arcs[160][54].adj = mgraph.arcs[54][160].adj =40 ;
    mgraph.arcs[55][54].adj = mgraph.arcs[54][55].adj =50 ;
    mgraph.arcs[160][55].adj = mgraph.arcs[55][160].adj =40 ;
    mgraph.arcs[162][55].adj = mgraph.arcs[55][162].adj =30 ;
    mgraph.arcs[162][56].adj = mgraph.arcs[56][162].adj =90 ;
    mgraph.arcs[164][56].adj = mgraph.arcs[56][164].adj =60 ;
    mgraph.arcs[163][164].adj = mgraph.arcs[164][163].adj =120 ;
    mgraph.arcs[162][163].adj = mgraph.arcs[163][162].adj =110 ;
    mgraph.arcs[162][167].adj = mgraph.arcs[167][162].adj =40 ;
    mgraph.arcs[163][166].adj = mgraph.arcs[166][163].adj =70 ;
    mgraph.arcs[163][67].adj = mgraph.arcs[67][163].adj =40 ;
    mgraph.arcs[68][67].adj = mgraph.arcs[67][68].adj =40 ;
    mgraph.arcs[166][68].adj = mgraph.arcs[68][166].adj =40 ;
    mgraph.arcs[166][165].adj = mgraph.arcs[165][166].adj =80 ;
    mgraph.arcs[166][155].adj = mgraph.arcs[155][166].adj =40 ;
    mgraph.arcs[58][155].adj = mgraph.arcs[155][58].adj =120 ;
    mgraph.arcs[165][57].adj = mgraph.arcs[57][165].adj =30 ;
    mgraph.arcs[58][57].adj = mgraph.arcs[57][58].adj =85 ;
    mgraph.arcs[172][57].adj = mgraph.arcs[57][172].adj =60 ;
    mgraph.arcs[172][160].adj = mgraph.arcs[160][172].adj =90 ;
    mgraph.arcs[170][159].adj = mgraph.arcs[159][170].adj =90 ;
    mgraph.arcs[158][168].adj = mgraph.arcs[168][158].adj =90 ;
    mgraph.arcs[169][168].adj = mgraph.arcs[168][169].adj =30 ;
    mgraph.arcs[169][62].adj = mgraph.arcs[62][169].adj =30 ;
    mgraph.arcs[63][62].adj = mgraph.arcs[62][63].adj =30 ;
    mgraph.arcs[63][82].adj = mgraph.arcs[82][63].adj =60 ;
    mgraph.arcs[49][82].adj = mgraph.arcs[82][49].adj =60 ;
    mgraph.arcs[64][82].adj = mgraph.arcs[82][64].adj =80 ;
    mgraph.arcs[174][62].adj = mgraph.arcs[62][174].adj =70 ;
    mgraph.arcs[208][175].adj = mgraph.arcs[175][208].adj =55;
    mgraph.arcs[64][65].adj = mgraph.arcs[65][64].adj =20 ;
    mgraph.arcs[66][65].adj = mgraph.arcs[65][66].adj =30 ;
    mgraph.arcs[66][174].adj = mgraph.arcs[174][66].adj =30 ;
    mgraph.arcs[175][174].adj = mgraph.arcs[174][175].adj =40 ;
    mgraph.arcs[62][208].adj = mgraph.arcs[208][62].adj =30 ;
    mgraph.arcs[61][208].adj = mgraph.arcs[208][61].adj =30 ;
    mgraph.arcs[61][169].adj = mgraph.arcs[169][61].adj =40 ;
    mgraph.arcs[170][171].adj = mgraph.arcs[171][170].adj =30 ;
    mgraph.arcs[172][173].adj = mgraph.arcs[173][172].adj =30 ;
    mgraph.arcs[170][168].adj = mgraph.arcs[168][170].adj =60 ;
    mgraph.arcs[172][57].adj = mgraph.arcs[57][172].adj =60 ;
    mgraph.arcs[60][61].adj = mgraph.arcs[61][60].adj =30 ;
    mgraph.arcs[171][61].adj = mgraph.arcs[61][171].adj =30 ;
    mgraph.arcs[171][60].adj = mgraph.arcs[60][171].adj =30 ;
    mgraph.arcs[173][60].adj = mgraph.arcs[60][173].adj =30 ;
    mgraph.arcs[59][60].adj = mgraph.arcs[60][59].adj =20 ;
    mgraph.arcs[59][58].adj = mgraph.arcs[58][59].adj =20 ;
    mgraph.arcs[173][58].adj = mgraph.arcs[58][173].adj =40 ;
    mgraph.arcs[83][58].adj = mgraph.arcs[58][83].adj =30 ;
    mgraph.arcs[83][182].adj = mgraph.arcs[182][83].adj =20 ;
    mgraph.arcs[76][182].adj = mgraph.arcs[182][76].adj =15 ;
    mgraph.arcs[78][182].adj = mgraph.arcs[182][78].adj =15 ;
    mgraph.arcs[178][76].adj = mgraph.arcs[76][178].adj =25 ;
    mgraph.arcs[78][179].adj = mgraph.arcs[179][78].adj =25 ;
    mgraph.arcs[178][77].adj = mgraph.arcs[77][178].adj =15 ;
    mgraph.arcs[179][77].adj = mgraph.arcs[77][179].adj =15 ;
    mgraph.arcs[179][180].adj = mgraph.arcs[180][179].adj =70 ;
    mgraph.arcs[181][180].adj = mgraph.arcs[180][181].adj =25 ;
    mgraph.arcs[181][80].adj = mgraph.arcs[80][181].adj =60 ;
    mgraph.arcs[185][80].adj = mgraph.arcs[80][185].adj =70 ;
    mgraph.arcs[185][79].adj = mgraph.arcs[79][185].adj =80 ;
    mgraph.arcs[184][179].adj = mgraph.arcs[179][184].adj =50 ;
    mgraph.arcs[184][79].adj = mgraph.arcs[79][184].adj =40 ;
    mgraph.arcs[86][77].adj = mgraph.arcs[77][86].adj =45 ;
    mgraph.arcs[86][79].adj = mgraph.arcs[79][86].adj =45 ;
    mgraph.arcs[86][186].adj = mgraph.arcs[186][86].adj =15 ;
    mgraph.arcs[79][186].adj = mgraph.arcs[186][79].adj =40 ;
    mgraph.arcs[178][183].adj = mgraph.arcs[183][178].adj =50 ;
    mgraph.arcs[178][86].adj = mgraph.arcs[86][178].adj =45 ;
    mgraph.arcs[87][187].adj = mgraph.arcs[187][87].adj =20 ;
    mgraph.arcs[87][186].adj = mgraph.arcs[186][87].adj =20 ;
    mgraph.arcs[84][183].adj = mgraph.arcs[183][84].adj =80 ;
    mgraph.arcs[85][187].adj = mgraph.arcs[187][85].adj =80 ;
    mgraph.arcs[183][187].adj = mgraph.arcs[187][183].adj =15;
    mgraph.arcs[84][177].adj = mgraph.arcs[177][84].adj =120 ;
    mgraph.arcs[85][75].adj = mgraph.arcs[75][85].adj =15 ;
    mgraph.arcs[74][177].adj = mgraph.arcs[177][74].adj =20 ;
    mgraph.arcs[74][75].adj = mgraph.arcs[75][74].adj =25 ;
    mgraph.arcs[74][73].adj = mgraph.arcs[73][74].adj =60 ;
    mgraph.arcs[176][73].adj = mgraph.arcs[73][176].adj =30 ;
    mgraph.arcs[94][189].adj = mgraph.arcs[189][94].adj =50 ;
    mgraph.arcs[189][95].adj = mgraph.arcs[95][189].adj =30 ;
    mgraph.arcs[95][190].adj = mgraph.arcs[190][95].adj =30 ;
    mgraph.arcs[190][200].adj = mgraph.arcs[200][190].adj =40 ;
    mgraph.arcs[196][197].adj = mgraph.arcs[197][196].adj =20 ;
    mgraph.arcs[200][196].adj = mgraph.arcs[196][200].adj =80 ;
    mgraph.arcs[196][93].adj = mgraph.arcs[93][196].adj =180 ;
    mgraph.arcs[93][201].adj = mgraph.arcs[201][93].adj =50 ;
    mgraph.arcs[91][201].adj = mgraph.arcs[201][91].adj =20 ;
    mgraph.arcs[92][91].adj = mgraph.arcs[91][92].adj =60 ;
    mgraph.arcs[92][98].adj = mgraph.arcs[98][92].adj =40 ;
    mgraph.arcs[193][90].adj = mgraph.arcs[90][193].adj =40 ;
    mgraph.arcs[90][89].adj = mgraph.arcs[89][90].adj =50 ;
    mgraph.arcs[89][88].adj = mgraph.arcs[88][89].adj =40 ;
    mgraph.arcs[197][202].adj = mgraph.arcs[202][197].adj =190 ;
    mgraph.arcs[202][203].adj = mgraph.arcs[203][202].adj =30;
    mgraph.arcs[201][193].adj = mgraph.arcs[193][201].adj =15;
    mgraph.arcs[203][93].adj = mgraph.arcs[93][203].adj =65;
    mgraph.arcs[202][204].adj = mgraph.arcs[204][202].adj =200 ;
    mgraph.arcs[203][204].adj = mgraph.arcs[204][203].adj =200 ;
    mgraph.arcs[204][205].adj = mgraph.arcs[205][204].adj =150 ;
    mgraph.arcs[99][204].adj = mgraph.arcs[204][99].adj =100 ;
    mgraph.arcs[100][205].adj = mgraph.arcs[205][100].adj =120 ;
    mgraph.arcs[100][206].adj = mgraph.arcs[206][100].adj =70 ;
    mgraph.arcs[206][188].adj = mgraph.arcs[188][206].adj =60 ;
    mgraph.arcs[188][161].adj = mgraph.arcs[161][188].adj =80 ;
    mgraph.arcs[188][56].adj = mgraph.arcs[56][188].adj =90 ;
    mgraph.arcs[205][164].adj = mgraph.arcs[164][205].adj =70 ;
    mgraph.arcs[206][195].adj = mgraph.arcs[195][206].adj =110 ;
    mgraph.arcs[195][194].adj = mgraph.arcs[194][195].adj =90 ;
    mgraph.arcs[194][209].adj = mgraph.arcs[209][194].adj =140 ;
    mgraph.arcs[192][191].adj = mgraph.arcs[191][192].adj =100 ;
    mgraph.arcs[191][190].adj = mgraph.arcs[190][191].adj =100 ;
    mgraph.arcs[191][96].adj = mgraph.arcs[96][191].adj =60 ;
    mgraph.arcs[96][192].adj = mgraph.arcs[192][96].adj =40 ;
    mgraph.arcs[192][97].adj = mgraph.arcs[97][192].adj =50 ;
    mgraph.arcs[192][196].adj = mgraph.arcs[196][192].adj =60 ;
    mgraph.arcs[97][199].adj = mgraph.arcs[199][97].adj =80 ;
    mgraph.arcs[199][197].adj = mgraph.arcs[197][199].adj =30 ;
    mgraph.arcs[199][194].adj = mgraph.arcs[194][199].adj =110 ;
    mgraph.arcs[193][203].adj = mgraph.arcs[203][193].adj =65 ;
    mgraph.arcs[156][39].adj = mgraph.arcs[39][156].adj =40 ;
    mgraph.arcs[195][156].adj = mgraph.arcs[156][195].adj =200 ; mgraph.arcs[195][156].kind = mgraph.arcs[156][195].kind =false ;
    mgraph.arcs[209][130].adj = mgraph.arcs[130][209].adj =200 ;
    mgraph.arcs[209][117].adj = mgraph.arcs[117][209].adj =10 ;
    mgraph.arcs[209][191].adj = mgraph.arcs[191][209].adj =100 ;
}    //把各个点之间的权重写下

int heuristic(int start, int end) {
    // 启发式函数，可以使用曼哈顿距离或欧几里得距离,这里选用欧式距离
    typedef struct
    {
        int x;
        int y;

    }Point;
    Point pointList[MAX_VERTEX_NUM-1];
    int pointx[MAX_VERTEX_NUM-1]={ 228,  454,  598,  569,  977, 1169,  438,  405,  289,  284,
                                      285,  295,  301,  299,  597,  706,  758,  728,  451,  783,
                                      451,  751,  589,  570,  513,  690, 872, 1211, 1313, 1397,
                                      1366, 1130, 1125, 1131, 1418, 1265, 1496, 1532, 1526, 1211,
                                      1486, 1703, 1873, 2065, 2217, 1951, 1880, 1959, 2029, 1646,

                                      1593, 1630, 1703, 1778, 1850, 1651, 2257, 2425, 2387, 2350,
                                      2280, 2197, 2152, 2333, 2329, 2359, 2128, 2264, 2583, 2977,
                                      2974, 2978, 2997, 2977, 2976, 2747, 2897, 2757, 3182, 3039,
                                      1799, 2084, 2574, 2881, 2974, 3057, 3105,  458,  458,  458,
                                      316,  170,  389,  113,  174,  589,  664,  175, 1064, 1380,

                                      456,   634, 1160, 1265, 1122,  832,  615,  292,  905,  579,
                                      593,   589,  608,  603,  860,  845,  839, 1024, 1206, 1256,
                                      1419, 1013,  864,  910,  860, 1457,  852,  881,  750, 1388,
                                      1301,  1622, 1523, 1704, 1704, 1867, 1602, 1598, 1867, 1708,
                                      1876, 1880, 1974, 1979, 2211, 1703, 1865, 1799, 2066, 1757,

                                      1834, 1909, 2215, 2055, 2443, 1433, 1692, 1697, 1789, 1845,
                                      1740, 1888, 2051, 1658, 2186, 2306, 2041, 2043, 2139, 2110,
                                      2194, 2173, 2274, 2363, 2248, 2976, 2878, 2898, 2898, 2898,
                                      3026, 2755, 2896, 3090, 3221, 3119, 2966, 1609,  120,  311,
                                      598,  588,  464, 959,  1126, 402,  442,  442,  664,  306,

                                      392,  702,  682, 1158, 1478, 1366,  849, 2250, 845};

    int pointy[MAX_VERTEX_NUM-1]={ 250,  238,  215,  150,  229,  225,  639,  679,  802,  943,
                                      992, 1193, 1358, 1445, 1440, 1339, 1250, 1149, 1114, 1071,
                                      1011,  983,  884,  797,  712,  396,  567,  486,  668,  416,
                                      769,  786,  691, 1229, 1283, 1441, 1258, 1348, 1473, 1107,
                                      344,  494,  525,  698,  690,  999, 1126, 1271, 1376, 1605,

                                      1810, 1883, 2008, 2137, 2264, 2402, 2208, 2071, 2001, 1933,
                                      1802, 1678, 1591, 1365, 1429, 1514, 2705, 2614,  858,  246,
                                      467,  637,  956, 1193, 1305, 1973, 2039, 2108, 2044, 2462,
                                      865, 1480, 2041, 1557, 1562, 1916, 1812, 2690, 2615, 2477,
                                      2370, 2370, 2231, 1624, 1472, 1646, 1759, 2487, 2551, 2302,

                                      303,  273,  422,  586,  588,  377, 1014, 1118, 1146, 1122,
                                      1190, 1158, 1269, 1341, 1250, 1338, 1441, 1430,  914,  910,
                                      868, 1013,  710,  816,  850, 1374,  246,  369,  575, 1473,
                                      1050, 1400,  331,  335,  387,  225,  212,  235,  383,  678,
                                      680,  625,  624,  684,  373,  868,  877,  980,  883, 1267,

                                      1398, 1544,  875, 1168, 2366, 1568, 1710, 1887, 2029, 2153,
                                      2079, 2308, 2572, 2583, 2246, 2459, 1799, 1803, 1762, 1937,
                                      1898, 2070, 2014, 1690, 1754,  863, 1240, 1992, 2105, 2274,
                                      2301, 2037, 1814, 2178, 2323, 1898, 1808, 2150, 1473, 1490,
                                      1495, 1756, 2376, 1844, 2025, 1802, 1864, 1864, 1859, 1627,

                                      2371, 2304, 2370, 2398, 2587, 2156, 1029, 1754, 1495};
    for (int i = 0; i < MAX_VERTEX_NUM-1; ++i) {
        pointList[i].x = pointx[i];
        pointList[i].y = pointy[i];

    }
    if (start < 0 || start >= 209 || end < 0 || end >= 209) {
        return 0; // 或者抛出异常
    }
    int dx = pointList[start].x - pointList[end].x;
    int dy = pointList[start].y - pointList[end].y;
    return static_cast<int>( std::sqrt(std::pow(dx, 2) + std::pow(dy, 2))); // 返回欧几里得距离
}


Path FindWay::findPath(int startPos, int endPos, int waykind)  //A* 算法查找路径
{

    if (startPos == endPos) {
        Path a;
        a.path = QVector<int>(0);
        a.distance = QVector<int>(0);
        return a;
    }

    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> openList;
    std::vector<int> g_cost(MAX_VERTEX_NUM, INF);
    std::vector<int> prev(MAX_VERTEX_NUM, -1);
    std::vector<bool> closedList(MAX_VERTEX_NUM, false);

    g_cost[startPos] = 0;
    openList.push({startPos, 0, heuristic(startPos, endPos)});

    while (!openList.empty()) {
        Node current = openList.top();
        openList.pop();

        if (current.vertex == endPos) {
            break;
        }

        if (closedList[current.vertex]) {
            continue;
        }
        closedList[current.vertex] = true;

        for (int neighbor = 0; neighbor < MAX_VERTEX_NUM; ++neighbor) {
            if (mgraph.arcs[current.vertex][neighbor].adj == INF) {
                continue; // 无边连接
            }

            int tentative_g_cost = g_cost[current.vertex] + mgraph.arcs[current.vertex][neighbor].adj;
            if (tentative_g_cost < g_cost[neighbor]) {
                g_cost[neighbor] = tentative_g_cost;
                int f_cost = tentative_g_cost + heuristic(neighbor, endPos);
                openList.push({neighbor, tentative_g_cost, f_cost});
                prev[neighbor] = current.vertex;
            }
        }
    }

    Path result;
    QVector<int> path;
    QVector<int> distance;
    for (int at = endPos; at != -1; at = prev[at]) {
        path.push_back(at);
        if (prev[at] != -1) {
            distance.push_back(mgraph.arcs[at][prev[at]].adj);
        }
    }
    std::reverse(path.begin(), path.end());
    std::reverse(distance.begin(), distance.end());

    result.path = path;
    result.distance = distance;
    return result;
}

void FindWay::speek(char* Text) {
    FILE* fq = fopen("voice.vbs", "w");
    if (fq != NULL) {
        std::string safeText = Text;
        size_t pos = 0;
        while ((pos = safeText.find("\"", pos)) != std::string::npos) {
            safeText.replace(pos, 1, "\"\"");
            pos += 2;
        }

        // 创建 VBScript 脚本，允许中途停止
        fprintf(fq,
                "Dim speech\n"
                "Set speech = CreateObject(\"SAPI.SpVoice\")\n"
                "speech.Speak \"%s\"\n"
                "WScript.Sleep 10000  ' 假设这是语音持续时间\n"
                "speech.WaitUntilDone(10000)\n"
                "Set speech = Nothing\n", safeText.c_str());
        fclose(fq);

        // 使用 ShellExecuteW 执行脚本
        std::wstring script = L"cscript";
        std::wstring params = L"//nologo voice.vbs";
        ShellExecuteW(NULL, L"open", script.c_str(), params.c_str(), NULL, SW_HIDE);
    }
}


void FindWay::stopspeek() {
    // 创建一个新的 VBScript 文件来停止语音
    FILE* fq = fopen("stop_voice.vbs", "w");
    if (fq != NULL) {
        // 直接使用 WMI 结束进程的方法来停止语音
        fprintf(fq,
                "Set objWMIService = GetObject(\"winmgmts:{impersonationLevel=impersonate}!\")\n"
                "Set colProcess = objWMIService.ExecQuery(\"Select * from Win32_Process Where Name = 'cscript.exe'\")\n"
                "For Each objProcess in colProcess\n"
                "    objProcess.Terminate()\n"
                "Next\n");
        fclose(fq);

        // 执行停止脚本
        ShellExecuteW(NULL, L"open", L"cscript", L"//nologo stop_voice.vbs", NULL, SW_HIDE);
        system("del stop_voice.vbs");
    }
}
